//#include <iostream>
//
//int main() {
//    std::cout << "Hello, World!" << std::endl;
//    return 0;
//}

#include <iostream>
#include <vector>

//******************************************************************************************************* 表
//class SEQTABLE;
void SequentialList();

void MenuChoice();
void singlelinked_list();

void Table() {
//    std::cout << "Table" << std::endl;
//    std::cout << "1.顺序表*******2.单链表" << std::endl
//              << "0.break" << std::endl;
    int table_choice, tar = 0;
    while (1) {
        std::cout << "Table" << std::endl;
        std::cout << "1.顺序表*******2.单链表" << std::endl
                  << "0.break" << std::endl;
        std::cin >> table_choice;
        switch (table_choice) {
            case 0:
                tar = 1;
                break;
                //MenuChoice();              //主菜单
            case 1:
                SequentialList();
                break;
            case 2:
                singlelinked_list();
                break;
        }
        if (tar == 1) {
            return;
        }
    }
}

//--------------------------------------------------------------------------------------------- 顺序表
class SEQLIST {
public:
#define InitSize 10              //默认最大长度
    typedef struct {
        int *data;               //指示动态分配数组的指针
        int MaxSize;             //当前最大长度
        int len;                 //当前长度
    } SEQL;

    //**********************************************建
    void Init(SEQL &seql, int n) {
        seql.data = (int *) malloc(InitSize * sizeof(int));
        seql.MaxSize = InitSize;
        seql.len = 0;
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (seql.len == seql.MaxSize) {                //扩容
                int *p = seql.data;
                seql.data = (int *) malloc((seql.MaxSize + InitSize) * sizeof(int));
                for (int j = 0; j < seql.MaxSize; j++) {
                    seql.data[j] = p[j];
                }
                seql.MaxSize += InitSize;
                free(p);
            }
            std::cout << "第" << i << "个数：" << std::endl;
            std::cin >> x;
            seql.data[i] = x;
            seql.len += 1;
        }
        std::cout << std::endl;
        for (int all = 0; all < seql.len; all++) {           //输出
            std::cout << seql.data[all] << " ";
        }
        std::cout << std::endl;
        //SequentialList();
    }

    //**********************************************插
    void Insert(SEQL &seql, int x, int e) {
        if (x < 0 || x > seql.len + 1) {                         //判断
            std::cout << "x不合法" << std::endl;
            //SequentialList();
            return;
        }
        if (seql.len == seql.MaxSize - 1) {                //扩容
            int *p = seql.data;
            seql.data = (int *) malloc((seql.MaxSize + InitSize) * sizeof(int));
            for (int j = 0; j < seql.MaxSize; j++) {
                seql.data[j] = p[j];
            }
            seql.MaxSize += InitSize;
            free(p);
        }
        for (int i = seql.len - 1; i > x - 2; i--) {
            seql.data[i + 1] = seql.data[i];
        }
        seql.data[x - 1] = e;
        seql.len += 1;
        for (int all = 0; all < seql.len; all++) {           //输出
            std::cout << seql.data[all] << " ";
        }
        std::cout << std::endl;
        //SequentialList();
    }

    //**********************************************删位
    void PosDelate(SEQL &seql, int x) {
        if (x < 0 || x > seql.len) {
            std::cout << "位置不合法" << std::endl;
            //SequentialList();
            return;
        }
        for (int i = x; i < seql.len - 1; i++) {
            seql.data[i] = seql.data[i + 1];
        }
        seql.data[seql.len - 1] = NULL;
        seql.len--;
        std::cout << std::endl;
        for (int all = 0; all < seql.len; all++) {           //输出
            std::cout << seql.data[all] << " ";
        }
        std::cout << std::endl;
        //SequentialList();
    }

    //**********************************************删值
    void ValueDelate(SEQL &seql, int x) {
        int flag = 0;
        int i = 0;
        for (i = 0; i < seql.len; i++) {
            if (seql.data[i] == x) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            std::cout << "查无此值" << std::endl;
        } else {
            for (int j = i; j < seql.len - 1; j++) {
                seql.data[j] = seql.data[j + 1];
            }
            seql.data[seql.len - 1] = NULL;
            seql.len--;
            std::cout << std::endl;
            for (int all = 0; all < seql.len; all++) {           //输出
                std::cout << seql.data[all] << " ";
            }
            std::cout << std::endl;
        }
        //SequentialList();
    }

    //**********************************************改
    void Modify(SEQL &seql, int x, int v) {
        int flag = 0, i = 0;
        for (i = 0; i < seql.len; i++) {
            if (seql.data[i] == x) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            std::cout << "查无此值" << std::endl;
        } else {
            seql.data[i] = v;
            std::cout << std::endl;
            for (int all = 0; all < seql.len; all++) {           //输出
                std::cout << seql.data[all] << " ";
            }
            std::cout << std::endl;
        }
        //SequentialList();
    }

    //**********************************************值查位
    void ValFindPos(SEQL &seql, int x) {
        int flag = 0, i = 0;
        std::vector<int> vec;
        for (i = 0; i < seql.len; i++) {
            if (seql.data[i] == x) {
                flag = 1;
                //break;
                vec.push_back(i + 1);
            }
        }
        if (flag == 0) {
            std::cout << "查无此值" << std::endl;
        } else {
            //std::cout << "此值位置：" << i+1 << std::endl;
            for (int j = 0; j < vec.size(); j++) {
                std::cout << vec[j] << " ";
            }
            std::cout << std::endl;
        }
        //SequentialList();
    }

    //**********************************************位查值
    void PosFindVal(SEQL &seql, int x) {
        if (x < 0 || x > seql.len) {
            std::cout << "位置不合法" << std::endl;
        } else {
            std::cout << "此位置值为：" << seql.data[x] << std::endl;
        }
        //SequentialList();
    }

};

//**********************************************功能列表
void SequentialList() {
    SEQLIST SL;
    SEQLIST::SEQL seql;
    //std::cout << "1.建  2.插  3.删值  4.删位  5.修改  6.值查位  7.位查值  0.break" << std::endl;
    int seq_choice;
    //std::cin >> seq_choice;
    int tar = 0;
    while (1) {
        std::cout << "1.建  2.插  3.删值  4.删位  5.修改  6.值查位  7.位查值  0.break" << std::endl;
        std::cin >> seq_choice;
        switch (seq_choice) {
            case 0:
                tar = 1;
                break;
                //Table();
            case 1:
                std::cout << "大小？" << std::endl;
                int x;
                std::cin >> x;
                SL.Init(seql, x);
                //SequentialList();
                break;
            case 2:
                std::cout << "位置？" << std::endl;
                int pos02;
                std::cin >> pos02;
                std::cout << "数值？" << std::endl;
                int value02;
                std::cin >> value02;
                SL.Insert(seql, pos02, value02);
                break;
            case 3:
                std::cout << "值？" << std::endl;
                int value03;
                std::cin >> value03;
                SL.ValueDelate(seql, value03);
                break;
            case 4:
                std::cout << "位置？" << std::endl;
                int pos04;
                std::cin >> pos04;
                SL.PosDelate(seql, pos04);
                break;
            case 5:
                std::cout << "原？" << std::endl;
                int value05_old;
                std::cin >> value05_old;
                std::cout << "新？" << std::endl;
                int value05_new;
                std::cin >> value05_new;
                SL.Modify(seql, value05_old, value05_new);
                break;
            case 6:
                std::cout << "值？" << std::endl;
                int value06;
                std::cin >> value06;
                SL.ValFindPos(seql, value06);
                break;
            case 7:
                std::cout << "位置？" << std::endl;
                int pos07;
                std::cin >> pos07;
                SL.PosFindVal(seql, pos07);
                break;
        }
        if (tar == 1) {
            //break;
            return;
        }
    }
}

//---------------------------------------------------------------------------------------------单链表
//Single-linked list
void singlelinked_list();

class SLkList {
public:
    typedef struct LNode {
        int data;
        struct LNode *next;
    } LNode, *LinkList;

    //**********************************************建
    void Init(LinkList &L, int n) {
        L = (LNode *) malloc(sizeof(LNode));
        if (L == NULL) {                              //头节点正常分配
            std::cout << "内存不足" << std::endl;
            return;
        }
        L->data = NULL;
        L->next = NULL;
        LinkList N = (LinkList) malloc(sizeof(LNode));
        N = L;
        for (int i = 0; i < n; i++) {
            LNode *p = (LNode *) malloc(sizeof(LNode));
            N->next = p;
            p->next = NULL;
            N = p;
            std::cout << "第" << i + 1 << "个数：";
            std::cin >> N->data;
            //std::cout << std::endl;
        }
        for (int i = 0; i < n; i++) {                       //输出
            L = L->next;
            std::cout << L->data << " ";
            //N = N->next;
        }
        std::cout << std::endl;
    }

    //**********************************************插
    void Insert(LinkList &L, int x, int e) {
//        L = (LNode *) malloc(sizeof(LNode));
//        if (L == NULL) {                              //头节点正常分配
//            std::cout << "内存不足" << std::endl;
//            return;
//        }
//        L->data = NULL;
//        L->next = NULL;

        LinkList N = (LinkList) malloc(sizeof(LNode));
        N = L;
        if (N== NULL) {
            std::cout << "输入L有误" << std::endl;
            singlelinked_list();
        }
        if(x ==1 ){
            LNode *p = (LNode *) malloc(sizeof(LNode));
            p->data = e;
            p->next = N->next;
            N->next = p;
        } else {
            for (int i = 0; i < x - 1; i++) {
                if (N == NULL) {
                    std::cout << "位置有误" << std::endl;
                    singlelinked_list();
                }
                N = N->next;
            }
            LNode *p = (LNode *) malloc(sizeof(LNode));
            p->data = e;
            p->next = N->next;
            N->next = p;
        }
        while(L !=NULL){                            //输出
            L = L->next;
            std::cout << L->data << " ";
            //L = L->next;
            if(L->next == NULL){
                return;
            }
        }
        std::cout << std::endl;
    }
//**********************************************删值
void ValueDelate(LinkList &L, int e){
        LNode *N = (LNode *) malloc(sizeof (LNode));
        if(L == NULL){
            std::cout << "表空！" << std::endl;
            singlelinked_list();
        }
        while (L->next != NULL){
            L = L->next;
            if(L->next->data == e){
                L->next = L->next->next;
            }
        }
        while(L !=NULL){                            //输出
            L = L->next;
            std::cout << L->data << " ";
            //L = L->next;
        }
        std::cout << std::endl;
    }


};


//**********************************************功能列表
void singlelinked_list() {
    SLkList slk;
    SLkList::LNode *slnode;
    int slk_choice = 0;
    int tar = 0;                              //退出
    int n = 0;                                //数量
    int x = 0;                                //位置
    int e = 0;                                //数值
    while (1) {
        std::cout << "1.建  2.插  3.删值  4.删位  5.修改  6.值查位  7.位查值  0.break" << std::endl;
        std::cin >> slk_choice;
        switch (slk_choice) {
            case 0:
                tar = 1;
                break;
            case 1:
                std::cout << "节点数：";
                std::cin >> n;
                std::cout << std::endl;
                slk.Init(slnode, n);
                n = 0;
                break;
            case 2:
                std::cout << "插入的位置:";
                std::cin >> x;
                std::cout << "值：";
                std::cin >> e;
                slk.Insert(slnode, x, e);
                x = 0;
                e = 0;
                break;
            case 3:
                std::cout << "要删的值：";
                std::cin >> e;
                slk.ValueDelate(slnode,e);
                e = 0;
                break;
        }
        if (tar == 1) {
            return;
        }
    }
}


//*******************************************************************************************************
void MenuChoice() {
//    std::cout << "Data Structure" << std::endl;
//    std::cout << "1.表" << std::endl;
//    std::cout << "0.break" << std::endl;
    int menu_choice, tar = 0;
    while (1) {
        std::cout << "Data Structure" << std::endl;
        std::cout << "1.表" << std::endl;
        std::cout << "0.break" << std::endl;
        std::cin >> menu_choice;
        //if (menu_choice == 0) { return; }
        switch (menu_choice) {
            case 0:
                tar = 1;
                break;
            case 1:
                Table();
                break;
                //Table();
        }
        if (tar == 1) {
            return;
        }
    }
}


//*******************************************************************************************************
int main() {
    std::cout << "Hello, World!" << std::endl;
    MenuChoice();
    return 0;
}


//#include <iostream>
//class A{
//public:
//    virtual void fun() = 0;
//};
//class B : public A{
//public:
//    void fun(){
//        std::cout << "123" << std::endl;
//    }
//};


//#include <iostream>
//
//class Base
//{
//public:
//    Base(){}
//    void callFunc();
//    virtual ~Base(){};
//private:
//    virtual void Func() = 0;
//};
//class Derived:public Base
//{
//public:
//    Derived(){}
//private:
//    virtual void Func();
//};
//void Base::Func()
//{
//    std::cout << "func in Base!" << std::endl;
//}
//void Base::callFunc()
//{
//    Func();
//    Base::Func();//静态调用纯虚函数
//}
//void Derived::Func()
//{
//    std::cout << "func in Derived!" << std::endl;
//}
//int main()
//{
//    Base *pd = new Derived;
//    pd->callFunc();
//    delete pd;
//    //system("pause");
//    return 0;
//}

//#include <iostream>
//
//class Base{
//public:
//    Base();
//    int y = 1;
//    void FunCall();
//    ~Base();
//
////private:
//    virtual void Func() = 0;
//};
//
//void Base::FunCall(){
//    Base::Func();
//}
//
//void Base::Func() {
//    std::cout << "abc" << std::endl;
//    y++;
//    std::cout << y;
//}
//
//int main(){
//    Base *b;
//    //b->FunCall();
//    b->Base::Func();
//    //b->Func();
//    return 0;
//}